package lc;

import java.util.*;


import org.junit.*;

public class Ex241 {
    class Solution1 {
        public List<Integer> diffWaysToCompute(String expression) {
            if (expression == null || expression.length() == 0)
                return new ArrayList<>();
            // 记录已经计算出来的值
            map = new HashMap<>();
            return helper(expression);
        }

        Map<String, List<Integer>> map;

        public List<Integer> helper(String s) {
            if (s.length() == 0) {
                return new ArrayList<>();
            }
            if (map.containsKey(s))
                return map.get(s);
            char[] cs = s.toCharArray();
            int res = 0, len = cs.length;
            int i;
            for (i = 0; i < len; i++) {
                if (!isOperation(cs[i])) {
                    res = res * 10 + cs[i] - '0';
                } else {
                    break;
                }
            }
            // 只有一个数字
            if (i == len) {
                List<Integer> result = Arrays.asList(res);
                map.put(s, result);
                return result;
            }

            // 后序得到所有左右数字的划分方案结果，按照各自的划分方案进行这次的计算
            List<Integer> left, right, cur = new ArrayList<>();

            for (int j = 0; j < len; j++) {
                if (isOperation(cs[j])) {
                    left = helper(s.substring(0, j));
                    right = helper(s.substring(j + 1));
                    for (int k = 0; k < left.size(); k++) {
                        for (int l = 0; l < right.size(); l++) {
                            // 左右所有组合的解
                            cur.add(caculate(left.get(k), cs[j], right.get(l)));
                        }
                    }
                }
            }
            map.put(s, cur);
            return cur;
        }

        private int caculate(int num1, char c, int num2) {
            switch (c) {
                case '+':
                    return num1 + num2;
                case '-':
                    return num1 - num2;
                case '*':
                    return num1 * num2;
            }
            return -1;
        }

        private boolean isOperation(char c) {
            return c == '+' || c == '-' || c == '*';
        }
    }

    class Solution {
        // 动态规划解法
        /*
         * 先将expression处理为nums和cals的两个组合 状态定义：List<Integer>[][] f :从i到j的所有可能的解
         * 
         * 遍历起始和结束下标的手法值的学习
         */
        public List<Integer> diffWaysToCompute(String expression) {

            List<Integer> nums = new ArrayList<>();
            List<Character> cals = new ArrayList<>();
            char[] cs = expression.toCharArray();
            for (int i = 0; i < cs.length; i++) {
                if (!isOperation(cs[i])) {
                    int t = 0, j;
                    for (j = i; j < cs.length && !isOperation(cs[j]); j++) {
                        t = t * 10 + cs[j] - '0';
                    }
                    i = j - 1;
                    nums.add(t);
                } else {
                    cals.add(cs[i]);
                }
            }
            int m = nums.size();
            List<Integer>[][] f = (ArrayList<Integer>[][]) new ArrayList[m][m];
            List<Integer> res;

            // 只有一个数字
            for (int i = 0; i < m; i++) {
                res = new ArrayList<>();
                res.add(nums.get(i));
                f[i][i] = res;
            }

            // 2个以上的数字
            List<Integer> left, right;
            for (int cnt = 2; cnt <= m; cnt++) {
                for (int i = 0; i < m; i++) { // f 开始下标
                    int j = cnt + i - 1; // f结束下标
                    if (j >= m)
                        break;
                    res = new ArrayList<>();
                    for (int t = i; t < j; t++) {
                        left = f[i][t];
                        right = f[t + 1][j];
                        for (int k = 0; k < left.size(); k++) {
                            for (int l = 0; l < right.size(); l++) {
                                // 左右所有组合的解
                                /* 
                                    这里尤其注意：
                                    运算符下标与左数字下标一致
                                */
                                res.add(caculate(left.get(k), cals.get(t), right.get(l)));
                            }
                        }
                        
                    }
                    f[i][j] = (ArrayList<Integer>) res;
                }
            }
            return f[0][m - 1];
        }

        private int caculate(int num1, char c, int num2) {
            switch (c) {
                case '+':
                    return num1 + num2;
                case '-':
                    return num1 - num2;
                case '*':
                    return num1 * num2;
            }
            return -1;
        }

        private boolean isOperation(char c) {
            return c == '+' || c == '-' || c == '*';
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.diffWaysToCompute("2*3-4*5"));
    }
}
